package exam;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class test2 {
    public static void main(String[] args) {
String s=s = "ADOBECODEBANC";

        String t = "ABC";
        System.out.println(minWindow1(s, t));

    }

    public static String minWindow(String ss, String tt) {
char[]s=ss.toCharArray();
char[]t=tt.toCharArray();

int []hash1=new int[128];
int []hash2=new int[128];
int kinds=0;
int begin=-1;
int minLen=Integer.MAX_VALUE;
        for (int i = 0; i <t.length ; i++) {
            if(hash1[t[i]]++==0)kinds++;
        }

        for (int left=0,right=0,count=0;right<s.length;right++){
            char in=s[right];
            if(++hash2[in]==hash1[in]){
                count++;
            }
            while(count==kinds){
                if(right-left+1<minLen){
                    minLen=right-left+1;
                    begin=left;
                }
                char out=s[left++];
                if(hash2[out]--==hash1[out]){
                    count--;
                }
            }
        }
        if(begin==-1)return new String();
        else return ss.substring(begin,begin+minLen);
    }



    public static String minWindow1(String s, String t) {
int minlen=Integer.MAX_VALUE;
int ml=0;
int mr=0;
        HashMap<Character,Integer>map=new HashMap<>();
        for (int i = 0; i <t.length() ; i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i),0)+1);
        }
HashMap<Character,Integer>map1=new HashMap<>();
        for (int left = 0,right=0,count=0; right <s.length() ; right++) {

            char ch=s.charAt(right);
            map1.put(ch,map1.getOrDefault(ch,0)+1);
if (map1.get(ch)<= map.getOrDefault(ch,0)){
    count++;
}
if(count==t.length()){
    while(!map.containsKey(s.charAt(left))){
        left++;
    }

    minlen=Math.min(minlen,right-left+1);
    if(minlen==right-left+1){
        ml=left;
        mr=right;
    }

    map1.put(s.charAt(left),map1.get(s.charAt(left)-1));
    left++;
    count--;
}
        }
        return s.substring(ml,mr);
    }


    public List<Integer> findSubstring(String s, String[] words) {
List<Integer>list=new ArrayList<>();
        HashMap<String,Integer>map1=new HashMap<>();
        int len=words[0].length();
        int m= words.length;

        for (int i = 0; i <m ; i++) {
            map1.put(words[i], map1.getOrDefault(words[i],0)+1 );
        }
        for (int i = 0; i <len ; i++) {
            HashMap<String,Integer>map2=new HashMap<>();
            for (int right =i,left=i,count=0; right+len <=s.length() ; right+=len) {
                String in=s.substring(right,right+len);
                map2.put(in,map2.getOrDefault(in,0)+1);
                if(map2.get(in)<= map1.getOrDefault(in,0)){
                    count++;
                }
                if (right-left+1>len*m){
                    String out=s.substring(left,left+len);
                    if (map2.get(out)<= map1.getOrDefault(out,0)){
                        count--;
                    }
                    map2.put(out,map2.get(out)-1);
                    left+=len;
                }
                if (count==m){
                    list.add(left);
                }
            }
        }
return list;
    }
}
